ABC 160 D - Line++

問題

1からNまでの番号がついた頂点を持つ無向グラフGがある。

GのN - 1までの各頂点はi + 1に対して辺を持っている。

簡単に言うと、頂点１から頂点Nまでが一本の辺でまっすぐ繋がっているということだ。

例外として、XとYという数値が与えられ、頂点Xと頂点Yは繋がっている。

まっすぐなグラフの中に一本だけショートカットのルートが存在するという感じだ。

このようなグラフについて頂点iと頂点jの最短距離がk(1..N-1)になるものの数をそれぞれ求めよという問題

制約

3 <= N <= 2 * 10^3

1 <= X,Y <= N

X + 1 < Y

回答

きりみんちゃんはこの問題をACするのに4時間近く費やしたんだけど、まずはそのACした回答から見ていきたいと思う。

これは最適解ではないので読み飛ばしても構わない。

code:Kotlin

fun problem160d(n: Int, x: Int, y: Int): String {

val routes = Array(n) { mutableListOf<Int>() }

for (i in 0 until n - 1) {

}

val distances= Array(n - 1) { IntArray(n) { -1 } }

val counts = hashMapOf<Int, Int>()

for (i in 0 until n - 1) {

val queue = ArrayDeque<Int>()

queue.offer(i)

while(!queue.isEmpty()) {

val current = queue.poll()

queue.offer(next)

}

}

}

}

val ans = Array(n - 1) { 0 }

var count = 0

for (i in counts) {

count++

}

return ans.joinToString("\n")

}

これは何をしているかというと、全ての頂点に対して幅優先探索を行い、最短距離を求めている。

そしてそれぞれの頂点から他の頂点への最短距離をメモしておき、それらを足し合わせることで答えを出している。

最初は「これは常に実質一方通行なので、単方向リストで十分なのでは」と考えた。

しかしよくよく考えると、入力例3のようなケースではそれが通用しないことに気づいた。

https://gyazo.com/8f44ad30841ef491c867de7494bdb6a5

この例では、赤が正しい最短距離で、水色は間違った最短距離である。

自分より後ろの頂点しか探索しない単方向リストではこのような場合に頂点４は３を経由したルートに気づくことが出来ず、水色の距離を出してしまう。

これを回避するためにはやはり次のようなコードでグラフを双方向にする必要があった。

code:Kotlin

val routes = Array(n) { mutableListOf<Int>() }

for (i in 0 until n - 1) {

}

しかし、双方向リストにしてしまうと今度は１→２と２→１が両方集計されてしまうという問題が発生した。

それを回避しているのが次の部分だ。

code:Kotlin

}

ここでdrop(i + 1)をすることにより、最短距離を探索し終わったあとで、今の頂点より前の頂点に関する集計を除外している。

例えば頂点４を探索するとdropをしていない状態では次のような状態になっている。(ちなみにDropはListから指定した数の要素を捨てる関数です)

code:Kotlin

ここで前から3, 2, 1は頂点４から頂点１，２，３への距離のため、頂点１～３で探索して集計した内容と重複してしまう。

なのでdorp(i + 1)を使って後半の１(頂点５までの距離)，２(頂点６までの距離)，２(頂点７までの距離)だけを残すようにした。

BFSを使ったもっとうまい探索

こちらのエントリで紹介されているBFSを使った解法。

パッと見では理解出来なかったので前述した解法でACしたが、こちらを読み解いていきたいと思う。

コード

code:C++

using namespace std;

int main() {

int N, X, Y;

cin >> N >> X >> Y;

--X, --Y;

vector<vector<int>> dist(N, vector<int>(N, -1));

for (int s = 0; s < N; ++s) {

queue<int> que;

que.push(s);

while (!que.empty()) {

auto v = que.front(); que.pop();

vector<int> nvs;

if (v > 0) nvs.push_back(v-1);

if (v < N-1) nvs.push_back(v+1);

if (v == X) nvs.push_back(Y);

if (v == Y) nvs.push_back(X);

for (auto nv : nvs) {

que.push(nv);

}

}

}

}

vector<int> res(N, 0);

for (int i = 0; i < N; ++i) {

}

}

distというのはdistanceのことで、距離の一覧を持ったリストをN個(頂点分)保持した二重リストだ。中身は全て-１で初期化されている。

vというのがキューから取り出した探索起点で、nvsというのはその中で探索すべき辺の一覧のようだ。

code:C++

for (auto nv : nvs) {

que.push(nv);

}

}

まずはこの部分を見ていこう。

一般的なBFSではこの形式でvから辿れる頂点を全て調べて、すでに探索済みでなければその巡れる頂点を次の探索起点としてキューに追加するとともに距離を+１する。

この部分はその処理そのもののようだ。

次にその上のif文が並んでいるところをみて見よう。

なにやら判定処理をたくさんしている。

code:C++

if (v > 0) nvs.push_back(v-1);

これは、v が0以上だったらキューにv-1を追加している。

vが0以下(要するに０)とはどういう状況だろうか。

それはvが頂点０の時である。

つまり頂点0でなければ頂点vの一つ前も辺があるとみなし探索対象にしているようだ。

code:C++

if (v < N-1) nvs.push_back(v+1);

こちは逆の端を判定しただけで上とほぼ同じ処理ですね。

頂点N - 1でなければ頂点vの一つ後も辺があるとみなし探索対象にしているようだ。

code:C++

if (v == X) nvs.push_back(Y);

これはvがXだったらYを辺として追加している。

ぱっと見よくわからない。

が、よくよく考えると、Xとはグラフ上で唯一の分岐が発生する地点である。

そしてYとはその行き先のことだ。

※再掲

https://gyazo.com/8f44ad30841ef491c867de7494bdb6a5

ここまで考えれば、vがXであったならvからYへの辺があるとみなすのが当たり前であることに気がつく。

code:C++

if (v == Y) nvs.push_back(X);

これは上の式でやっている辺の定義の逆向きをしているだけだ。

そして最後に集計部分を見てみよう。

code:C++

vector<int> res(N, 0);

for (int i = 0; i < N; ++i) {

}

これは2重ループをして、i < jについて距離を集計していっているだけだ。

なるほど確かにこちらの方が効率的だしシンプルである。

というわけでKotlinで写経してAC出来ることを確認しました。

code:Kotlin

fun problem160d(n: Int, x: Int, y: Int): String {

val dist = Array(n) { IntArray(n) { -1 } }

for (s in 0 until n) {

val que = ArrayDeque<Int>()

que.offer(s)

while (!que.isEmpty()) {

val v = que.poll()

val nvs = mutableListOf<Int>()

if (v > 0) nvs.add(v - 1)

if (v < n - 1) nvs.add(v + 1)

if (v == x - 1) nvs.add(y - 1)

if (v == y - 1) nvs.add(x - 1)

for (nv in nvs) {

que.offer(nv)

}

}

}

}

val res = IntArray(n) { 0 }

for (i in 0 until n) {

for (j in i + 1 until n) {

}

}

return res.drop(1).joinToString("\n")

}

しかもこの回答でも結局のところ双方向部分が重複するのは同じで、きりみんちゃんはその重複を上手く削れずにTLEになってしまったため、countsというHashMapを使うことで最適化してゴリ押しでACさせたけど、なんとこれは単純に2重ループのjをi + 1にするだけでよかったのだ。

きりみんちゃんってホント馬鹿...。

謎の超シンプル解法

ところでこの問題の解法をググると、多くの人がもっと短い謎の計算式によって解いているようだ。

せっかくなのでこちらの解法の謎も解明していきたいと思う。

解説者によって多少の差はあるものの、なにやらminを使って答えを求めていることが共通しているようだ。

こちらの解説を読み解いてみよう。

code:C++

using namespace std;

int main(){

int n,x,y;cin>>n>>x>>y;

for(int i=1;i<n;i++){

for(int j=i+1;j<n+1;j++){

int dd=min(j-i,abs(i-x)+1+abs(j-y));

}

}

}

ぱっと見ただけでは全く理解が出来ないけど、なんかめちゃくちゃシンプルである。

順番に解読していこうと思う。解説にはこのように書かれている。

iからjにたどり着く方法は、頂点Xと頂点Yの間の辺を使うか、使わないかの2通りしかありません。そして、それぞれの距離は、以下の式で表されます。

・頂点Xと頂点Yの間の辺を使う場合

距離 = |i – X| + 1 + |j-Y|

|i – X| = 頂点iから頂点Xの距離、1 = 頂点Xと頂点Yの距離、|j-Y| = 頂点jから頂点Yの距離

・頂点Xと頂点Yの間の辺を使わない場合

距離 = j – i

それぞれの場合において、上の2通りの距離のうち小さいほうが(i,j)の最短距離となります。

と書かれている。

これはどういうことだろうか。

まず下の

頂点Xと頂点Yの間の辺を使わない場合　距離 = j – i

について考えてみよう。

これは問題のグラフが一直線であり、常に頂点iの次に頂点i + 1が来るということを考えると、なんとなく分かる気がする。

図に書くとこういう感じだ。なるほど。

※緑の部分

https://gyazo.com/bbeeb3e8f01b4844efabfd7aa80fe716

ここまでは簡単だけど、次はややこしそうだ。

・ 頂点Xと頂点Yの間の辺を使う場合

距離 = |i – X| + 1 + |j-Y|

|i – X| = 頂点iから頂点Xの距離、1 = 頂点Xと頂点Yの距離、|j-Y| = 頂点jから頂点Yの距離

？？？？？

とりあえず実装してみた。

code:Kotlin

fun problem160d(n: Int, x: Int, y: Int): String {

val ans = IntArray(n - 1) { 0 }

for (i in 1 until n) {

for (j in i + 1 until n + 1) {

debugLog("i", i, "j", j, j - i, abs(i - x) + 1 + abs(j - y), "min:", min(j - i, abs(i - x) + 1 + abs(j - y)))

val distance = min(j - i, abs(i - x) + 1 + abs(j - y))

}

}

return ans.joinToString("\n")

}

なるほど確かに正しい結果になる。

デバッグログをみてみよう。とりあえずi = 1のケース。

code:Kotlin

ではなぜ正しく判定できるのか。

これは図を描いてみたら理解できた。

https://gyazo.com/779840c9a9207187e866dea577ff51df

水色がj - iで、赤色がabs(i - x) + 1 + abs(j - y)です。

abs(i - X)とはiからX(分岐点)までの距離だ。

次にabs(j - Y)とはY(分岐の行き先)からjまでの距離だ。

そして+1とはxからyに行くためのステップ数！！！！

そして水色の値と赤色の値のminを取ることで、どちらがより近いルートかが分かるのだ！！！！！

凄い！こんなことコンテスト中に考えられる人おる？？？？？？？？？